#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from l import l


class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class Solution:
    """
    @param head: The head of linked list.
    @return: You should return the head of the sorted linked list, using constant space complexity.
    """
    def sortList(self, head):
        # new_head, new_tail = self.quick_sort(head)
        # return new_head

        return self.merge_sort(head)

    def merge_sort(self, node):
        if (not node) or (not node.next):
            return node

        mid = self.find_mid(node)
        # print('mid %s' % mid.val)
        # print('mid next %s' % mid.next.val)
        left = node
        right = mid.next
        mid.next = None             # 这里一定要断开

        left_head = self.merge_sort(left)
        right_head = self.merge_sort(right)
        return self.merge_merged(left_head, right_head)

    def merge_merged(self, n1, n2):
        new_head = new_tail = ListNode('v', None)
        while n1 and n2:
            if n1.val <= n2.val:
                new_tail.next = n1
                n1 = n1.next
            else:
                new_tail.next = n2
                n2 = n2.next
            new_tail = new_tail.next

        # if n1:
        #     new_tail.next = n1
        # else:
        #     new_tail.next = n2
        new_tail.next = n1 or n2

        return new_head.next

    def find_mid(self, node):
        if (not node) or (not node.next):
            return node

        slow = node
        fast = node

        # print('slow %s' % getattr(slow, 'val', None))
        # print('fast %s' % getattr(fast, 'val', None))

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            # print('slow %s' % getattr(slow, 'val', None))
            # print('fast %s' % getattr(fast, 'val', None))
            # print('fast.next %s %s' % (fast.next, bool(fast.next)))
            # print('fast.next.next %s %s' % (fast.next.next, bool(fast.next.next)))

            # print('fast.next %s' % fast.next)
        return slow

    def quick_sort(self, lead_node):
        if lead_node is None:
            return None, None

        if lead_node.next is None:
            return lead_node, lead_node

        pivot = lead_node.val
        left, same_head, same_tail, right = self.split_list(lead_node, pivot)
        # show(left)
        # show(right)

        left_head, left_tail = self.quick_sort(left)
        right_head, right_tail = self.quick_sort(right)
        return self.merge_quick(
            left_head, left_tail,
            same_head, same_tail,
            right_head, right_tail
        )

    def merge_quick(self, left_head, left_tail, same_head, same_tail, right_head, right_tail):
        assert bool(left_head) == bool(left_tail)
        assert bool(right_head) == bool(right_tail)
        assert (same_head) and (same_tail)

        if left_head:
            left_tail.next = same_head
        else:
            left_head = same_head

        if right_head:
            same_tail.next = right_head
        else:
            right_tail = same_tail

        return left_head, right_tail

    def split_list(self, lead_node, pivot):
        # return real left, real right
        node = lead_node

        left_head  = left_tail  = ListNode('v', None)
        same_head  = same_tail  = ListNode('v', None)       # 把相同的提出来, 避免再排序这部分
        right_head = right_tail = ListNode('v', None)

        while(node):
            if node.val < pivot:
                left_tail.next = node
                left_tail = node
            elif node.val == pivot:
                same_tail.next = node
                same_tail = node
            else:
                right_tail.next = node
                right_tail = node
            node = node.next

        # 斩断牵连
        left_tail.next = same_tail.next = right_tail.next = None

        if same_tail.val == 'v':
            same_tail = None

        return left_head.next, same_head.next, same_tail, right_head.next


def show(n):
    while n:
        print("%s ----> " % n.val, sep=' ', end=' ')
        n = n.next
    print()


def make_link_list(py_list):
    dum_head = dum_tail = ListNode('v', None)

    for i in py_list:
        dummy_head = ListNode(i, None)
        dum_tail.next = dummy_head
        dum_tail = dummy_head

    return dum_head.next

def main():
    print("start main")

    v5 = ListNode(5)
    v4 = ListNode(4, v5)
    v3 = ListNode(10, v4)
    v2 = ListNode(2, v3)
    v1 = ListNode(2, v2)
    v0 = ListNode(2, v1)
    vm = ListNode(100, v0)
    show(vm)

    print(len(l))
    v = make_link_list(l)
    # show(v)
    s = Solution()
    ret = s.sortList(v)
    # node = s.find_mid(v)
    # print(node.val)
    # print(node.next.val)
    # print(node.next.next.val)
    # print(node.next.next.nexxt.val)
    # show(ret)

if __name__ == "__main__":
    main()
